package algorithms;

import java.util.Scanner;


public class Permutation {
	int N;
	
	public Permutation(int N) {
		this.N = N;
	}

//序数法
	public int fac(int i){	//factorial阶乘
		if(i < 0){
			System.out.println("请输入一个大于等于0的整数！");
			return -1;
		} else if(i == 0 || i == 1){
			return 1;
		} else {
			return i*fac(i-1);
		}
	}
	
	public int[] toFacNum(int num) {	//转换成阶乘进制
		int[] a = new int[N];
		for(int i = 0;i<N;i++){
			a[i] = 0;
		}
		for(int i = 1,j = 2;;j++){
			
			int e = num%j;
			num = num/j;
			if(num != 0){
				a[i++] = e;
			} else {
				a[i++] = e;
				break;
			}
		}
		return a;
	}
	
	public int[] FactoPermutation(int[] facNum) {	//阶乘进制转换为排列
		int[] arr = new int[N];
		int[] pointer = new int[N];
		for(int i = 0;i < N;i++){
			arr[i] = 0;
			pointer[i] = i;
		}
		
		for(int i = facNum.length - 1;i >= 0;i--){
			int p = facNum[i];
			int index = pointer[p];
			arr[index] = i + 1;
			while(p < N - 1){
				pointer[p] = pointer[p+1];
				p++;
			}
		}
		return arr;
	}
	
	public void ordinalOrder(){
		for(int i = 0;i < fac(N);i++){
			int[] arr = FactoPermutation(toFacNum(i));
			for(int j = N-1;j >= 0;j--){
				System.out.print(arr[j]);
			}
			
			System.out.println("");
		}
	}

//字典序法
	public int[] nextDictOrder(int[] arr) {
		int m = 0,n = 0;
		for(int i = 1;i < arr.length;i++){
			if(arr[i-1] < arr[i]){
				m = i;
			}
		}
		
		for(int i = m;i < arr.length;i++){
			if(arr[m - 1] < arr[i]){
				n = i;
			}
		}
		
		int tmp = arr[m-1];
		arr[m-1] = arr[n];
		arr[n] = tmp;
		
		int len = arr.length-1;
		for(int i = m;i < (m+arr.length)/2;){
			tmp = arr[i];
			arr[i] = arr[len];
			arr[len] = tmp;
			i++;
			len--;
		}
		return arr;
	}
	public void dictOrder() {
		int[]	arr = new int[N];
		for(int i = 0;i < N;i++){
			arr[i] = i+1;
		}
		
		for(int i = 0;i < N;i++){	//初始序列
			System.out.print(arr[i]);
		}
		System.out.println("");
		
		for(int i = 1;i < fac(N);i++){
			arr = nextDictOrder(arr);
			for(int j = 0;j < arr.length;j++){
				System.out.print(arr[j]);
			}
			System.out.println("");
		}
		
	}
	
//换位法
	class TranStruct {
		int[] arr;
		int[] stat;
		public TranStruct() {
			arr = new int[N];
			stat = new int[N];
		}
	}
	public TranStruct nextTransOrder(TranStruct ts) {
		int maxIndex = 0,maxNum = 0;
		
		for(int i = 0;i<ts.stat.length;i++){
			if(ts.stat[i] == -1){	//-1表示箭头向左
				if(i != 0){
					if(ts.arr[i] > ts.arr[i-1]){	//该数大于箭头所指方向的数字，则是活动状态
						if(ts.arr[i] > maxNum){	//该数是最大活动数
							maxNum = ts.arr[i];
							maxIndex = i;
							
						}
					}
				}
			}
			if(ts.stat[i] == 1){	//1表示箭头向右
				if(i != ts.stat.length-1){
					if(ts.arr[i] > ts.arr[i+1]){	//该数处于活动状态
						if(ts.arr[i] > maxNum){	//该数是最大活动数
							maxNum = ts.arr[i];
							maxIndex = i;
						}
					}
				}
			}
			
		}
		
		if(maxNum != 0){
			if(ts.stat[maxIndex] == -1){
				int tmp = ts.arr[maxIndex];
				ts.arr[maxIndex] = ts.arr[maxIndex-1];
				ts.arr[maxIndex-1] = tmp;
				
				int statTmp = ts.stat[maxIndex];
				ts.stat[maxIndex] = ts.stat[maxIndex-1];
				ts.stat[maxIndex-1] = statTmp;	
			}else if(ts.stat[maxIndex] == 1){
				int tmp = ts.arr[maxIndex];
				ts.arr[maxIndex] = ts.arr[maxIndex+1];
				ts.arr[maxIndex+1] = tmp;
				
				int statTmp = ts.stat[maxIndex];
				ts.stat[maxIndex] = ts.stat[maxIndex+1];
				ts.stat[maxIndex+1] = statTmp;
			}
			for(int i = 0;i < ts.arr.length;i++){
				if(ts.arr[i] > maxNum){
					ts.stat[i] = -ts.stat[i];	//所有比最大活动数大的数改变方向
				}
			}
		}
		
		return ts;
	}
	
	public void transOrder(){
		TranStruct tranStruct = new TranStruct();
		for(int i = 0;i < N;i++){
			tranStruct.arr[i] = i+1;
			tranStruct.stat[i] = -1;
		}
		
		for(int i = 0;i < N;i++){	//初始序列
			System.out.print(tranStruct.arr[i]);
		}
		System.out.println("");
		
		for(int i = 1;i < fac(N);i++){
			tranStruct = nextTransOrder(tranStruct);
			for(int j = 0;j < N;j++){
				System.out.print(tranStruct.arr[j]);
			}
			System.out.println("");
		}
	}
	
	
	public void setN() {	//获取元素个数
		Scanner in = new Scanner(System.in);
		N = in.nextInt();
		in.close();
	}

}
